home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 24 / CU Amiga Magazine's Super CD-ROM 24 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-07].iso / CUCD / Utilities / vim-5.1 / src / regexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-06  |  60.2 KB  |  2,620 lines
  1. /* vi:set ts=8 sts=4 sw=4:
  2.  *
  3.  * Handling of regular expressions: vim_regcomp(), vim_regexec(), vim_regsub()
  4.  *
  5.  * NOTICE:
  6.  *
  7.  * This is NOT the original regular expression code as written by Henry
  8.  * Spencer.  This code has been modified specifically for use with the VIM
  9.  * editor, and should not be used apart from compiling VIM.  If you want a
  10.  * good regular expression library, get the original code.  The copyright
  11.  * notice that follows is from the original.
  12.  *
  13.  * END NOTICE
  14.  *
  15.  *    Copyright (c) 1986 by University of Toronto.
  16.  *    Written by Henry Spencer.  Not derived from licensed software.
  17.  *
  18.  *    Permission is granted to anyone to use this software for any
  19.  *    purpose on any computer system, and to redistribute it freely,
  20.  *    subject to the following restrictions:
  21.  *
  22.  *    1. The author is not responsible for the consequences of use of
  23.  *        this software, no matter how awful, even if they arise
  24.  *        from defects in it.
  25.  *
  26.  *    2. The origin of this software must not be misrepresented, either
  27.  *        by explicit claim or by omission.
  28.  *
  29.  *    3. Altered versions must be plainly marked as such, and must not
  30.  *        be misrepresented as being the original software.
  31.  *
  32.  * Beware that some of this code is subtly aware of the way operator
  33.  * precedence is structured in regular expressions.  Serious changes in
  34.  * regular-expression syntax might require a total rethink.
  35.  *
  36.  * Changes have been made by Tony Andrews, Olaf 'Rhialto' Seibert, Robert Webb
  37.  * and Bram Moolenaar.
  38.  */
  39.  
  40. #include "vim.h"
  41.  
  42. #undef DEBUG
  43.  
  44. #include <stdio.h>
  45. #include "option.h"
  46.  
  47. /*
  48.  * The "internal use only" fields in regexp.h are present to pass info from
  49.  * compile to execute that permits the execute phase to run lots faster on
  50.  * simple cases.  They are:
  51.  *
  52.  * regstart    char that must begin a match; '\0' if none obvious
  53.  * reganch    is the match anchored (at beginning-of-line only)?
  54.  * regmust    string (pointer into program) that match must include, or NULL
  55.  * regmlen    length of regmust string
  56.  *
  57.  * Regstart and reganch permit very fast decisions on suitable starting points
  58.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  59.  * of lines that cannot possibly match.  The regmust tests are costly enough
  60.  * that vim_regcomp() supplies a regmust only if the r.e. contains something
  61.  * potentially expensive (at present, the only such thing detected is * or +
  62.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  63.  * supplied because the test in vim_regexec() needs it and vim_regcomp() is
  64.  * computing it anyway.
  65.  */
  66.  
  67. /*
  68.  * Structure for regexp "program".  This is essentially a linear encoding
  69.  * of a nondeterministic finite-state machine (aka syntax charts or
  70.  * "railroad normal form" in parsing technology).  Each node is an opcode
  71.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  72.  * all nodes except BRANCH and BRACES_COMPLEX implement concatenation; a "next"
  73.  * pointer with a BRANCH on both ends of it is connecting two alternatives.
  74.  * (Here we have one of the subtle syntax dependencies:    an individual BRANCH
  75.  * (as opposed to a collection of them) is never concatenated with anything
  76.  * because of operator precedence).  The "next" pointer of a BRACES_COMPLEX
  77.  * node points to the node after the stuff to be repeated.  The operand of some
  78.  * types of node is a literal string; for others, it is a node leading into a
  79.  * sub-FSM.  In particular, the operand of a BRANCH node is the first node of
  80.  * the branch.    (NB this is *not* a tree structure: the tail of the branch
  81.  * connects to the thing following the set of BRANCHes.)  The opcodes are:
  82.  */
  83.  
  84. /* definition    number           opnd?    meaning */
  85. #define END        0    /* no    End of program. */
  86. #define BOL        1    /* no    Match "" at beginning of line. */
  87. #define EOL        2    /* no    Match "" at end of line. */
  88. #define ANY        3    /* no    Match any one character. */
  89. #define ANYOF        4    /* str    Match any character in this string. */
  90. #define ANYBUT        5    /* str    Match any character not in this
  91.                  *    string. */
  92. #define BRANCH        6    /* node Match this alternative, or the
  93.                  *    next... */
  94. #define BACK        7    /* no    Match "", "next" ptr points backward. */
  95. #define EXACTLY        8    /* str    Match this string. */
  96. #define NOTHING        9    /* no    Match empty string. */
  97. #define STAR        10    /* node Match this (simple) thing 0 or more
  98.                  *    times. */
  99. #define PLUS        11    /* node Match this (simple) thing 1 or more
  100.                  *    times. */
  101. #define BRACE_SIMPLE    12    /* node Match this (simple) thing between m and
  102.                  *    n times (\{m,n\}). */
  103. #define BOW        13    /* no    Match "" after [^a-zA-Z0-9_] */
  104. #define EOW        14    /* no    Match "" at    [^a-zA-Z0-9_] */
  105. #define IDENT        15    /* no    Match identifier char */
  106. #define WORD        16    /* no    Match keyword char */
  107. #define FNAME        17    /* no    Match file name char */
  108. #define PRINT        18    /* no    Match printable char */
  109. #define SIDENT        19    /* no    Match identifier char but no digit */
  110. #define SWORD        20    /* no    Match word char but no digit */
  111. #define SFNAME        21    /* no    Match file name char but no digit */
  112. #define SPRINT        22    /* no    Match printable char but no digit */
  113. #define BRACE_LIMITS    23    /* 2int    define the min & max for BRACE_SIMPLE
  114.                  *    and BRACE_COMPLEX. */
  115. #define WHITE        24    /* no    Match whitespace char */
  116. #define NWHITE        25    /* no    Match non-whitespace char */
  117. #define MOPEN        30 /* -39  no    Mark this point in input as start of
  118.                  *    \( subexpr. */
  119. #define MCLOSE        40 /* -49  no    Analogous to MOPEN. */
  120. #define BACKREF        50 /* -59  node Match same string again \1-\9 */
  121. #define BRACE_COMPLEX    60 /* -69  node Match nodes between m & n times */
  122.  
  123. #define Magic(x)    ((x) | ('\\' << 8))
  124.  
  125. /*
  126.  * Opcode notes:
  127.  *
  128.  * BRANCH    The set of branches constituting a single choice are hooked
  129.  *        together with their "next" pointers, since precedence prevents
  130.  *        anything being concatenated to any individual branch.  The
  131.  *        "next" pointer of the last BRANCH in a choice points to the
  132.  *        thing following the whole choice.  This is also where the
  133.  *        final "next" pointer of each individual branch points; each
  134.  *        branch starts with the operand node of a BRANCH node.
  135.  *
  136.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  137.  *        exists to make loop structures possible.
  138.  *
  139.  * STAR,PLUS    '=', and complex '*' and '+', are implemented as circular
  140.  *        BRANCH structures using BACK.  Simple cases (one character
  141.  *        per match) are implemented with STAR and PLUS for speed
  142.  *        and to minimize recursive plunges.
  143.  *        Note: We would like to use "\?" instead of "\=", but a "\?"
  144.  *        can be part of a pattern to escape the special meaning of '?'
  145.  *        at the end of the pattern in "?pattern?e".
  146.  *
  147.  * BRACE_LIMITS    This is always followed by a BRACE_SIMPLE or BRACE_COMPLEX
  148.  *        node, and defines the min and max limits to be used for that
  149.  *        node.
  150.  *
  151.  * MOPEN,MCLOSE    ...are numbered at compile time.
  152.  */
  153.  
  154. /*
  155.  * A node is one char of opcode followed by two chars of "next" pointer.
  156.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  157.  * value is a positive offset from the opcode of the node containing it.
  158.  * An operand, if any, simply follows the node.  (Note that much of the
  159.  * code generation knows about this implicit relationship.)
  160.  *
  161.  * Using two bytes for the "next" pointer is vast overkill for most things,
  162.  * but allows patterns to get big without disasters.
  163.  */
  164. #define OP(p)        ((int)*(p))
  165. #define NEXT(p)        (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  166. #define OPERAND(p)    ((p) + 3)
  167. #define OPERAND_MIN(p)    (((*((p)+3)&0377)<<8) + (*((p)+4)&0377))
  168. #define OPERAND_MAX(p)    (((*((p)+5)&0377)<<8) + (*((p)+6)&0377))
  169.  
  170. /*
  171.  * Utility definitions.
  172.  */
  173. #ifndef CHARBITS
  174. # define UCHARAT(p)    ((int)*(unsigned char *)(p))
  175. #else
  176. # define UCHARAT(p)    ((int)*(p)&CHARBITS)
  177. #endif
  178.  
  179. #define EMSG_RETURN(m) { emsg(m); rc_did_emsg = TRUE; return NULL; }
  180.  
  181. #define MAX_LIMIT    32767
  182.  
  183. static int re_ismult __ARGS((int));
  184. static int cstrncmp __ARGS((char_u *s1, char_u *s2, int n));
  185. static char_u *cstrchr __ARGS((char_u *, int));
  186.  
  187. #ifdef DEBUG
  188. static void    regdump __ARGS((char_u *, vim_regexp *));
  189. static char_u    *regprop __ARGS((char_u *));
  190. #endif
  191.  
  192.     static int
  193. re_ismult(c)
  194.     int c;
  195. {
  196.     return (c == Magic('*') || c == Magic('+') || c == Magic('=') ||
  197.         c == Magic('{'));
  198. }
  199.  
  200. /*
  201.  * Flags to be passed up and down.
  202.  */
  203. #define HASWIDTH    01    /* Known never to match null string. */
  204. #define SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  205. #define SPSTART        04    /* Starts with * or +. */
  206. #define WORST        0    /* Worst case. */
  207.  
  208. /*
  209.  * When regcode is set to this value, code is not emitted and size is computed
  210.  * instead.
  211.  */
  212. #define JUST_CALC_SIZE    ((char_u *) -1)
  213.  
  214. static char_u        *reg_prev_sub;
  215.  
  216. /*
  217.  * REGEXP_INRANGE contains all characters which are always special in a []
  218.  * range after '\'.
  219.  * REGEXP_ABBR contains all characters which act as abbreviations after '\'.
  220.  * These are:
  221.  *  \r    - New line (CR).
  222.  *  \t    - Tab (TAB).
  223.  *  \e    - Escape (ESC).
  224.  *  \b    - Backspace (Ctrl('H')).
  225.  */
  226. static char_u REGEXP_INRANGE[] = "]^-\\";
  227. static char_u REGEXP_ABBR[] = "rteb";
  228.  
  229. static int    backslash_trans __ARGS((int c));
  230. static char_u * skip_range __ARGS((char_u *p));
  231.  
  232.     static int
  233. backslash_trans(c)
  234.     int        c;
  235. {
  236.     switch (c)
  237.     {
  238.     case 'r':   return CR;
  239.     case 't':   return TAB;
  240.     case 'e':   return ESC;
  241.     case 'b':   return Ctrl('H');
  242.     }
  243.     return c;
  244. }
  245.  
  246. /*
  247.  * Skip over a "[]" range.
  248.  * "p" must point to the character after the '['.
  249.  * The returned pointer is on the matching ']', or the terminating NUL.
  250.  */
  251.     static char_u *
  252. skip_range(p)
  253.     char_u    *p;
  254. {
  255.     int            cpo_lit;        /* 'cpoptions' contains 'l' flag */
  256.  
  257.     cpo_lit = (!reg_syn && vim_strchr(p_cpo, CPO_LITERAL) != NULL);
  258.  
  259.     if (*p == '^')    /* Complement of range. */
  260.     ++p;
  261.     if (*p == ']' || *p == '-')
  262.     ++p;
  263.     while (*p != NUL && *p != ']')
  264.     {
  265.     if (*p == '-')
  266.     {
  267.         ++p;
  268.         if (*p != ']' && *p != '\0')
  269.         ++p;
  270.     }
  271.     else if (*p == '\\'
  272.         && (vim_strchr(REGEXP_INRANGE, p[1]) != NULL
  273.             || (!cpo_lit && vim_strchr(REGEXP_ABBR, p[1]) != NULL)))
  274.         p += 2;
  275.     else
  276.         ++p;
  277.     }
  278.  
  279.     return p;
  280. }
  281.  
  282. /*
  283.  * Global work variables for vim_regcomp().
  284.  */
  285.  
  286. static char_u    *regparse;  /* Input-scan pointer. */
  287. static int    num_complex_braces; /* Complex \{...} count */
  288. static int    regnpar;    /* () count. */
  289. static char_u    *regcode;    /* Code-emit pointer, or JUST_CALC_SIZE */
  290. static long    regsize;    /* Code size. */
  291. static char_u    **regendp;    /* Pointer to endp array */
  292. static int    brace_min[10];    /* Minimums for complex brace repeats */
  293. static int    brace_max[10];    /* Maximums for complex brace repeats */
  294. static int    brace_count[10]; /* Current counts for complex brace repeats */
  295. static int    had_eol;    /* TRUE when EOL found by vim_regcomp() */
  296. static int    reg_magic;    /* p_magic passed to vim_regexec() */
  297.  
  298. /*
  299.  * META contains all characters that may be magic, except '^' and '$'.
  300.  */
  301.  
  302. static char_u META[] = ".[()|=+*<>iIkKfFpPsS~123456789{";
  303.  
  304. /*
  305.  * Forward declarations for vim_regcomp()'s friends.
  306.  */
  307. static void    initchr __ARGS((char_u *));
  308. static int    getchr __ARGS((void));
  309. static int    peekchr __ARGS((void));
  310. #define PeekChr() curchr    /* shortcut only when last action was peekchr() */
  311. static int    curchr;
  312. static void    skipchr __ARGS((void));
  313. static void    ungetchr __ARGS((void));
  314. static char_u    *reg __ARGS((int, int *));
  315. static char_u    *regbranch __ARGS((int *));
  316. static char_u    *regpiece __ARGS((int *));
  317. static char_u    *regatom __ARGS((int *));
  318. static char_u    *regnode __ARGS((int));
  319. static char_u    *regnext __ARGS((char_u *));
  320. static void    regc __ARGS((int));
  321. static void    unregc __ARGS((void));
  322. static void    reginsert __ARGS((int, char_u *));
  323. static void    reginsert_limits __ARGS((int, int, int, char_u *));
  324. static int    read_limits __ARGS((int, int, int *, int *));
  325. static void    regtail __ARGS((char_u *, char_u *));
  326. static void    regoptail __ARGS((char_u *, char_u *));
  327.  
  328. /*
  329.  * Skip past regular expression.
  330.  * Stop at end of 'p' of where 'dirc' is found ('/', '?', etc).
  331.  * Take care of characters with a backslash in front of it.
  332.  * Skip strings inside [ and ].
  333.  */
  334.     char_u *
  335. skip_regexp(p, dirc, magic)
  336.     char_u  *p;
  337.     int        dirc;
  338.     int        magic;
  339. {
  340.     for (; p[0] != NUL; ++p)
  341.     {
  342.     if (p[0] == dirc)    /* found end of regexp */
  343.         break;
  344.     if ((p[0] == '[' && magic) || (p[0] == '\\' && p[1] == '[' && !magic))
  345.         p = skip_range(p + 1);
  346.     else if (p[0] == '\\' && p[1] != NUL)
  347.         ++p;    /* skip next character */
  348.     }
  349.     return p;
  350. }
  351.  
  352. /*
  353.  * vim_regcomp - compile a regular expression into internal code
  354.  *
  355.  * We can't allocate space until we know how big the compiled form will be,
  356.  * but we can't compile it (and thus know how big it is) until we've got a
  357.  * place to put the code.  So we cheat:  we compile it twice, once with code
  358.  * generation turned off and size counting turned on, and once "for real".
  359.  * This also means that we don't allocate space until we are sure that the
  360.  * thing really will compile successfully, and we never have to move the
  361.  * code and thus invalidate pointers into it.  (Note that it has to be in
  362.  * one piece because vim_free() must be able to free it all.)
  363.  *
  364.  * Does not use reg_ic, see vim_regexec() for that.
  365.  *
  366.  * Beware that the optimization-preparation code in here knows about some
  367.  * of the structure of the compiled regexp.
  368.  */
  369.     vim_regexp *
  370. vim_regcomp(exp, magic)
  371.     char_u    *exp;
  372.     int        magic;
  373. {
  374.     vim_regexp    *r;
  375.     char_u    *scan;
  376.     char_u    *longest;
  377.     int        len;
  378.     int        flags;
  379.  
  380.     if (exp == NULL)
  381.     EMSG_RETURN(e_null);
  382.  
  383.     reg_magic = magic;
  384.  
  385.     /* First pass: determine size, legality. */
  386.     initchr((char_u *)exp);
  387.     num_complex_braces = 0;
  388.     regnpar = 1;
  389.     regsize = 0L;
  390.     regcode = JUST_CALC_SIZE;
  391.     regendp = NULL;
  392.     had_eol = FALSE;
  393.     regc(MAGIC);
  394.     if (reg(0, &flags) == NULL)
  395.     return NULL;
  396.  
  397.     /* Small enough for pointer-storage convention? */
  398. #ifdef SMALL_MALLOC        /* 16 bit storage allocation */
  399.     if (regsize >= 65536L - 256L)
  400.     EMSG_RETURN(e_toolong);
  401. #endif
  402.  
  403.     /* Allocate space. */
  404.     r = (vim_regexp *)lalloc(sizeof(vim_regexp) + regsize, TRUE);
  405.     if (r == NULL)
  406.     return NULL;
  407.  
  408.     /* Second pass: emit code. */
  409.     initchr((char_u *)exp);
  410.     num_complex_braces = 0;
  411.     regnpar = 1;
  412.     regcode = r->program;
  413.     regendp = r->endp;
  414.     regc(MAGIC);
  415.     if (reg(0, &flags) == NULL)
  416.     {
  417.     vim_free(r);
  418.     return NULL;
  419.     }
  420.  
  421.     /* Dig out information for optimizations. */
  422.     r->regstart = '\0';        /* Worst-case defaults. */
  423.     r->reganch = 0;
  424.     r->regmust = NULL;
  425.     r->regmlen = 0;
  426.     scan = r->program + 1;    /* First BRANCH. */
  427.     if (OP(regnext(scan)) == END)   /* Only one top-level choice. */
  428.     {
  429.     scan = OPERAND(scan);
  430.  
  431.     /* Starting-point info. */
  432.     if (OP(scan) == BOL)
  433.     {
  434.         r->reganch++;
  435.         scan = regnext(scan);
  436.     }
  437.     if (OP(scan) == EXACTLY)
  438.         r->regstart = *OPERAND(scan);
  439.     else if ((OP(scan) == BOW || OP(scan) == EOW)
  440.          && OP(regnext(scan)) == EXACTLY)
  441.         r->regstart = *OPERAND(regnext(scan));
  442.  
  443.     /*
  444.      * If there's something expensive in the r.e., find the longest
  445.      * literal string that must appear and make it the regmust.  Resolve
  446.      * ties in favor of later strings, since the regstart check works
  447.      * with the beginning of the r.e. and avoiding duplication
  448.      * strengthens checking.  Not a strong reason, but sufficient in the
  449.      * absence of others.
  450.      */
  451.     /*
  452.      * When the r.e. starts with BOW, it is faster to look for a regmust
  453.      * first. Used a lot for "#" and "*" commands. (Added by mool).
  454.      */
  455.     if (flags & SPSTART || OP(scan) == BOW || OP(scan) == EOW)
  456.     {
  457.         longest = NULL;
  458.         len = 0;
  459.         for (; scan != NULL; scan = regnext(scan))
  460.         if (OP(scan) == EXACTLY && STRLEN(OPERAND(scan)) >= (size_t)len)
  461.         {
  462.             longest = OPERAND(scan);
  463.             len = STRLEN(OPERAND(scan));
  464.         }
  465.         r->regmust = longest;
  466.         r->regmlen = len;
  467.     }
  468.     }
  469. #ifdef DEBUG
  470.     regdump(exp, r);
  471. #endif
  472.     return r;
  473. }
  474.  
  475. /*
  476.  * Check if during the previous call to vim_regcomp the EOL item "$" has been
  477.  * found.  This is messy, but it works fine.
  478.  */
  479.     int
  480. vim_regcomp_had_eol()
  481. {
  482.     return had_eol;
  483. }
  484.  
  485. /*
  486.  * reg - regular expression, i.e. main body or parenthesized thing
  487.  *
  488.  * Caller must absorb opening parenthesis.
  489.  *
  490.  * Combining parenthesis handling with the base level of regular expression
  491.  * is a trifle forced, but the need to tie the tails of the branches to what
  492.  * follows makes it hard to avoid.
  493.  */
  494.     static char_u *
  495. reg(paren, flagp)
  496.     int            paren;    /* Parenthesized? */
  497.     int            *flagp;
  498. {
  499.     char_u    *ret;
  500.     char_u    *br;
  501.     char_u    *ender;
  502.     int        parno = 0;
  503.     int        flags;
  504.  
  505.     *flagp = HASWIDTH;        /* Tentatively. */
  506.  
  507.     /* Make an MOPEN node, if parenthesized. */
  508.     if (paren)
  509.     {
  510.     if (regnpar >= NSUBEXP)
  511.         EMSG_RETURN(e_toombra);
  512.     parno = regnpar;
  513.     regnpar++;
  514.     ret = regnode(MOPEN + parno);
  515.     if (regendp)
  516.         regendp[parno] = NULL;  /* haven't seen the close paren yet */
  517.     }
  518.     else
  519.     ret = NULL;
  520.  
  521.     /* Pick up the branches, linking them together. */
  522.     br = regbranch(&flags);
  523.     if (br == NULL)
  524.     return NULL;
  525.     if (ret != NULL)
  526.     regtail(ret, br);    /* MOPEN -> first. */
  527.     else
  528.     ret = br;
  529.     if (!(flags & HASWIDTH))
  530.     *flagp &= ~HASWIDTH;
  531.     *flagp |= flags & SPSTART;
  532.     while (peekchr() == Magic('|'))
  533.     {
  534.     skipchr();
  535.     br = regbranch(&flags);
  536.     if (br == NULL)
  537.         return NULL;
  538.     regtail(ret, br);    /* BRANCH -> BRANCH. */
  539.     if (!(flags & HASWIDTH))
  540.         *flagp &= ~HASWIDTH;
  541.     *flagp |= flags & SPSTART;
  542.     }
  543.  
  544.     /* Make a closing node, and hook it on the end. */
  545.     ender = regnode((paren) ? MCLOSE + parno : END);
  546.     regtail(ret, ender);
  547.  
  548.     /* Hook the tails of the branches to the closing node. */
  549.     for (br = ret; br != NULL; br = regnext(br))
  550.     regoptail(br, ender);
  551.  
  552.     /* Check for proper termination. */
  553.     if (paren && getchr() != Magic(')'))
  554.     EMSG_RETURN(e_toombra)
  555.     else if (!paren && peekchr() != '\0')
  556.     {
  557.     if (PeekChr() == Magic(')'))
  558.         EMSG_RETURN(e_toomket)
  559.     else
  560.         EMSG_RETURN(e_trailing)    /* "Can't happen". */
  561.     /* NOTREACHED */
  562.     }
  563.     /*
  564.      * Here we set the flag allowing back references to this set of
  565.      * parentheses.
  566.      */
  567.     if (paren && regendp)
  568.     regendp[parno] = ender;    /* have seen the close paren */
  569.     return ret;
  570. }
  571.  
  572. /*
  573.  * regbranch - one alternative of an | operator
  574.  *
  575.  * Implements the concatenation operator.
  576.  */
  577.     static char_u    *
  578. regbranch(flagp)
  579.     int            *flagp;
  580. {
  581.     char_u        *ret;
  582.     char_u        *chain;
  583.     char_u        *latest;
  584.     int            flags;
  585.  
  586.     *flagp = WORST;        /* Tentatively. */
  587.  
  588.     ret = regnode(BRANCH);
  589.     chain = NULL;
  590.     while (peekchr() != '\0' && PeekChr() != Magic('|') &&
  591.                               PeekChr() != Magic(')'))
  592.     {
  593.     latest = regpiece(&flags);
  594.     if (latest == NULL)
  595.         return NULL;
  596.     *flagp |= flags & HASWIDTH;
  597.     if (chain == NULL)    /* First piece. */
  598.         *flagp |= flags & SPSTART;
  599.     else
  600.         regtail(chain, latest);
  601.     chain = latest;
  602.     }
  603.     if (chain == NULL)        /* Loop ran zero times. */
  604.     (void) regnode(NOTHING);
  605.  
  606.     return ret;
  607. }
  608.  
  609. /*
  610.  * regpiece - something followed by possible [*+=]
  611.  *
  612.  * Note that the branching code sequences used for = and the general cases
  613.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  614.  * both the endmarker for their branch list and the body of the last branch.
  615.  * It might seem that this node could be dispensed with entirely, but the
  616.  * endmarker role is not redundant.
  617.  */
  618.     static char_u *
  619. regpiece(flagp)
  620.     int            *flagp;
  621. {
  622.     char_u        *ret;
  623.     int            op;
  624.     char_u        *next;
  625.     int            flags;
  626.     int            minval;
  627.     int            maxval;
  628.  
  629.     ret = regatom(&flags);
  630.     if (ret == NULL)
  631.     return NULL;
  632.  
  633.     op = peekchr();
  634.     if (!re_ismult(op))
  635.     {
  636.     *flagp = flags;
  637.     return ret;
  638.     }
  639.     if (!(flags & HASWIDTH) && op != Magic('='))
  640.     EMSG_RETURN((char_u *)"*, \\+, or \\{ operand could be empty");
  641.     *flagp = (WORST | SPSTART);            /* default flags */
  642.  
  643.     skipchr();
  644.     if (op == Magic('*') && (flags & SIMPLE))
  645.     reginsert(STAR, ret);
  646.     else if (op == Magic('*'))
  647.     {
  648.     /* Emit x* as (x&|), where & means "self". */
  649.     reginsert(BRANCH, ret); /* Either x */
  650.     regoptail(ret, regnode(BACK));    /* and loop */
  651.     regoptail(ret, ret);    /* back */
  652.     regtail(ret, regnode(BRANCH));    /* or */
  653.     regtail(ret, regnode(NOTHING)); /* null. */
  654.     }
  655.     else if (op == Magic('+') && (flags & SIMPLE))
  656.     {
  657.     reginsert(PLUS, ret);
  658.     *flagp = (WORST | HASWIDTH);
  659.     }
  660.     else if (op == Magic('+'))
  661.     {
  662.     /* Emit x+ as x(&|), where & means "self". */
  663.     next = regnode(BRANCH); /* Either */
  664.     regtail(ret, next);
  665.     regtail(regnode(BACK), ret);    /* loop back */
  666.     regtail(next, regnode(BRANCH)); /* or */
  667.     regtail(ret, regnode(NOTHING)); /* null. */
  668.     *flagp = (WORST | HASWIDTH);
  669.     }
  670.     else if (op == Magic('='))
  671.     {
  672.     /* Emit x= as (x|) */
  673.     reginsert(BRANCH, ret); /* Either x */
  674.     regtail(ret, regnode(BRANCH));    /* or */
  675.     next = regnode(NOTHING);/* null. */
  676.     regtail(ret, next);
  677.     regoptail(ret, next);
  678.     }
  679.     else if (op == Magic('{') && (flags & SIMPLE))
  680.     {
  681.     if (!read_limits('{', '}', &minval, &maxval))
  682.         return NULL;
  683.     reginsert(BRACE_SIMPLE, ret);
  684.     reginsert_limits(BRACE_LIMITS, minval, maxval, ret);
  685.     if (minval > 0)
  686.         *flagp = (WORST | HASWIDTH);
  687.     }
  688.     else if (op == Magic('{'))
  689.     {
  690.     if (!read_limits('{', '}', &minval, &maxval))
  691.         return NULL;
  692.     if (num_complex_braces >= 10)
  693.         EMSG_RETURN((char_u *)"Too many complex \\{...}s");
  694.     reginsert(BRACE_COMPLEX + num_complex_braces, ret);
  695.     regoptail(ret, regnode(BACK));
  696.     regoptail(ret, ret);
  697.     reginsert_limits(BRACE_LIMITS, minval, maxval, ret);
  698.     if (minval > 0)
  699.         *flagp = (WORST | HASWIDTH);
  700.     ++num_complex_braces;
  701.     }
  702.     if (re_ismult(peekchr()))
  703.     EMSG_RETURN((char_u *)"Nested *, \\=, \\+, or \\{");
  704.  
  705.     return ret;
  706. }
  707.  
  708. /*
  709.  * regatom - the lowest level
  710.  *
  711.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  712.  * it can turn them into a single node, which is smaller to store and
  713.  * faster to run.
  714.  */
  715.     static char_u *
  716. regatom(flagp)
  717.     int           *flagp;
  718. {
  719.     char_u        *ret;
  720.     int            flags;
  721.     int            cpo_lit;        /* 'cpoptions' contains 'l' flag */
  722.  
  723.     *flagp = WORST;        /* Tentatively. */
  724.     cpo_lit = (!reg_syn && vim_strchr(p_cpo, CPO_LITERAL) != NULL);
  725.  
  726.     switch (getchr())
  727.     {
  728.       case Magic('^'):
  729.     ret = regnode(BOL);
  730.     break;
  731.       case Magic('$'):
  732.     ret = regnode(EOL);
  733.     had_eol = TRUE;
  734.     break;
  735.       case Magic('<'):
  736.     ret = regnode(BOW);
  737.     break;
  738.       case Magic('>'):
  739.     ret = regnode(EOW);
  740.     break;
  741.       case Magic('.'):
  742.     ret = regnode(ANY);
  743.     *flagp |= HASWIDTH | SIMPLE;
  744.     break;
  745.       case Magic('i'):
  746.     ret = regnode(IDENT);
  747.     *flagp |= HASWIDTH | SIMPLE;
  748.     break;
  749.       case Magic('k'):
  750.     ret = regnode(WORD);
  751.     *flagp |= HASWIDTH | SIMPLE;
  752.     break;
  753.       case Magic('I'):
  754.     ret = regnode(SIDENT);
  755.     *flagp |= HASWIDTH | SIMPLE;
  756.     break;
  757.       case Magic('K'):
  758.     ret = regnode(SWORD);
  759.     *flagp |= HASWIDTH | SIMPLE;
  760.     break;
  761.       case Magic('f'):
  762.     ret = regnode(FNAME);
  763.     *flagp |= HASWIDTH | SIMPLE;
  764.     break;
  765.       case Magic('F'):
  766.     ret = regnode(SFNAME);
  767.     *flagp |= HASWIDTH | SIMPLE;
  768.     break;
  769.       case Magic('p'):
  770.     ret = regnode(PRINT);
  771.     *flagp |= HASWIDTH | SIMPLE;
  772.     break;
  773.       case Magic('P'):
  774.     ret = regnode(SPRINT);
  775.     *flagp |= HASWIDTH | SIMPLE;
  776.     break;
  777.       case Magic('s'):
  778.     ret = regnode(WHITE);
  779.     *flagp |= HASWIDTH | SIMPLE;
  780.     break;
  781.       case Magic('S'):
  782.     ret = regnode(NWHITE);
  783.     *flagp |= HASWIDTH | SIMPLE;
  784.     break;
  785.       case Magic('('):
  786.     ret = reg(1, &flags);
  787.     if (ret == NULL)
  788.         return NULL;
  789.     *flagp |= flags & (HASWIDTH | SPSTART);
  790.     break;
  791.       case '\0':
  792.       case Magic('|'):
  793.       case Magic(')'):
  794.     EMSG_RETURN(e_internal)        /* Supposed to be caught earlier. */
  795.     /* NOTREACHED */
  796.       case Magic('='):
  797.     EMSG_RETURN((char_u *)"\\= follows nothing")
  798.     /* NOTREACHED */
  799.       case Magic('+'):
  800.     EMSG_RETURN((char_u *)"\\+ follows nothing")
  801.     /* NOTREACHED */
  802.       case Magic('{'):
  803.     EMSG_RETURN((char_u *)"\\{ follows nothing")
  804.     /* NOTREACHED */
  805.       case Magic('*'):
  806.     if (reg_magic)
  807.         EMSG_RETURN((char_u *)"* follows nothing")
  808.     else
  809.         EMSG_RETURN((char_u *)"\\* follows nothing")
  810.     /* break; Not Reached */
  811.       case Magic('~'):        /* previous substitute pattern */
  812.         if (reg_prev_sub)
  813.         {
  814.         char_u        *p;
  815.  
  816.         ret = regnode(EXACTLY);
  817.         p = reg_prev_sub;
  818.         while (*p)
  819.         {
  820.             regc(*p++);
  821.         }
  822.         regc('\0');
  823.         if (p - reg_prev_sub)
  824.         {
  825.             *flagp |= HASWIDTH;
  826.             if ((p - reg_prev_sub) == 1)
  827.             *flagp |= SIMPLE;
  828.         }
  829.         }
  830.         else
  831.         EMSG_RETURN(e_nopresub);
  832.         break;
  833.       case Magic('1'):
  834.       case Magic('2'):
  835.       case Magic('3'):
  836.       case Magic('4'):
  837.       case Magic('5'):
  838.       case Magic('6'):
  839.       case Magic('7'):
  840.       case Magic('8'):
  841.       case Magic('9'):
  842.         {
  843.         int            refnum;
  844.  
  845.         ungetchr();
  846.         refnum = getchr() - Magic('0');
  847.         /*
  848.          * Check if the back reference is legal. We use the parentheses
  849.          * pointers to mark encountered close parentheses, but this
  850.          * is only available in the second pass. Checking opens is
  851.          * always possible.
  852.          * Should also check that we don't refer to something that
  853.          * is repeated (+*=): what instance of the repetition should
  854.          * we match? TODO.
  855.          */
  856.         if (refnum < regnpar &&
  857.         (regendp == NULL || regendp[refnum] != NULL))
  858.         ret = regnode(BACKREF + refnum);
  859.         else
  860.         EMSG_RETURN((char_u *)"Illegal back reference");
  861.     }
  862.     break;
  863.       case Magic('['):
  864.     {
  865.         char_u    *p;
  866.  
  867.         /*
  868.          * If there is no matching ']', we assume the '[' is a normal
  869.          * character. This makes ":help [" work.
  870.          */
  871.         p = skip_range(regparse);
  872.         if (*p == ']')    /* there is a matching ']' */
  873.         {
  874.         /*
  875.          * In a character class, different parsing rules apply.
  876.          * Not even \ is special anymore, nothing is.
  877.          */
  878.         if (*regparse == '^') {        /* Complement of range. */
  879.             ret = regnode(ANYBUT);
  880.             regparse++;
  881.         }
  882.         else
  883.             ret = regnode(ANYOF);
  884.         if (*regparse == ']' || *regparse == '-')
  885.             regc(*regparse++);
  886.         while (*regparse != '\0' && *regparse != ']')
  887.         {
  888.             if (*regparse == '-')
  889.             {
  890.             regparse++;
  891.             if (*regparse == ']' || *regparse == '\0')
  892.                 regc('-');
  893.             else
  894.             {
  895.                 int        cclass;
  896.                 int        cclassend;
  897.  
  898.                 cclass = UCHARAT(regparse - 2) + 1;
  899.                 cclassend = UCHARAT(regparse);
  900.                 if (cclass > cclassend + 1)
  901.                 EMSG_RETURN(e_invrange);
  902.                 for (; cclass <= cclassend; cclass++)
  903.                 regc(cclass);
  904.                 regparse++;
  905.             }
  906.             }
  907.             /*
  908.              * Only "\]", "\^", "\]" and "\\" are special in Vi.  Vim
  909.              * accepts "\t", "\e", etc., but only when the 'l' flag in
  910.              * 'cpoptions' is not included.
  911.              */
  912.             else if (*regparse == '\\' &&
  913.                 (vim_strchr(REGEXP_INRANGE, regparse[1]) != NULL ||
  914.                  (!cpo_lit &&
  915.                    vim_strchr(REGEXP_ABBR, regparse[1]) != NULL)))
  916.             {
  917.             regparse++;
  918.             regc(backslash_trans(*regparse++));
  919.             }
  920.             else
  921.             regc(*regparse++);
  922.         }
  923.         regc('\0');
  924.         if (*regparse != ']')
  925.             EMSG_RETURN(e_toomsbra);
  926.         skipchr();        /* let's be friends with the lexer again */
  927.         *flagp |= HASWIDTH | SIMPLE;
  928.         break;
  929.         }
  930.     }
  931.     /* FALLTHROUGH */
  932.  
  933.       default:
  934.     {
  935.         int            len;
  936.         int            chr;
  937.  
  938.         ungetchr();
  939.         len = 0;
  940.         ret = regnode(EXACTLY);
  941.         /*
  942.          * Always take at least one character, for '[' without matching
  943.          * ']'.
  944.          */
  945.         while ((chr = peekchr()) != '\0' && (chr < Magic(0) || len == 0))
  946.         {
  947.         regc(chr);
  948.         skipchr();
  949.         len++;
  950.         }
  951. #ifdef DEBUG
  952.         if (len == 0)
  953.          EMSG_RETURN((char_u *)"Unexpected magic character; check META.");
  954. #endif
  955.         /*
  956.          * If there is a following *, \+ or \= we need the character
  957.          * in front of it as a single character operand
  958.          */
  959.         if (len > 1 && re_ismult(chr))
  960.         {
  961.         unregc();        /* Back off of *+= operand */
  962.         ungetchr();        /* and put it back for next time */
  963.         --len;
  964.         }
  965.         regc('\0');
  966.         *flagp |= HASWIDTH;
  967.         if (len == 1)
  968.         *flagp |= SIMPLE;
  969.     }
  970.     break;
  971.     }
  972.  
  973.     return ret;
  974. }
  975.  
  976. /*
  977.  * regnode - emit a node
  978.  */
  979.     static char_u *        /* Location. */
  980. regnode(op)
  981.     int        op;
  982. {
  983.     char_u  *ret;
  984.     char_u  *ptr;
  985.  
  986.     ret = regcode;
  987.     if (ret == JUST_CALC_SIZE)
  988.     {
  989.     regsize += 3;
  990.     return ret;
  991.     }
  992.     ptr = ret;
  993.     *ptr++ = op;
  994.     *ptr++ = '\0';        /* Null "next" pointer. */
  995.     *ptr++ = '\0';
  996.     regcode = ptr;
  997.  
  998.     return ret;
  999. }
  1000.  
  1001. /*
  1002.  * regc - emit (if appropriate) a byte of code
  1003.  */
  1004.     static void
  1005. regc(b)
  1006.     int        b;
  1007. {
  1008.     if (regcode != JUST_CALC_SIZE)
  1009.     *regcode++ = b;
  1010.     else
  1011.     regsize++;
  1012. }
  1013.  
  1014. /*
  1015.  * unregc - take back (if appropriate) a byte of code
  1016.  */
  1017.     static void
  1018. unregc()
  1019. {
  1020.     if (regcode != JUST_CALC_SIZE)
  1021.     regcode--;
  1022.     else
  1023.     regsize--;
  1024. }
  1025.  
  1026. /*
  1027.  * reginsert - insert an operator in front of already-emitted operand
  1028.  *
  1029.  * Means relocating the operand.
  1030.  */
  1031.     static void
  1032. reginsert(op, opnd)
  1033.     int        op;
  1034.     char_u     *opnd;
  1035. {
  1036.     char_u  *src;
  1037.     char_u  *dst;
  1038.     char_u  *place;
  1039.  
  1040.     if (regcode == JUST_CALC_SIZE)
  1041.     {
  1042.     regsize += 3;
  1043.     return;
  1044.     }
  1045.     src = regcode;
  1046.     regcode += 3;
  1047.     dst = regcode;
  1048.     while (src > opnd)
  1049.     *--dst = *--src;
  1050.  
  1051.     place = opnd;        /* Op node, where operand used to be. */
  1052.     *place++ = op;
  1053.     *place++ = '\0';
  1054.     *place = '\0';
  1055. }
  1056.  
  1057. /*
  1058.  * reginsert_limits - insert an operator in front of already-emitted operand.
  1059.  * The operator has the given limit values as operands.  Also set next pointer.
  1060.  *
  1061.  * Means relocating the operand.
  1062.  */
  1063.     static void
  1064. reginsert_limits(op, minval, maxval, opnd)
  1065.     int        op;
  1066.     int        minval;
  1067.     int        maxval;
  1068.     char_u     *opnd;
  1069. {
  1070.     char_u  *src;
  1071.     char_u  *dst;
  1072.     char_u  *place;
  1073.  
  1074.     if (regcode == JUST_CALC_SIZE)
  1075.     {
  1076.     regsize += 7;
  1077.     return;
  1078.     }
  1079.     src = regcode;
  1080.     regcode += 7;
  1081.     dst = regcode;
  1082.     while (src > opnd)
  1083.     *--dst = *--src;
  1084.  
  1085.     place = opnd;        /* Op node, where operand used to be. */
  1086.     *place++ = op;
  1087.     *place++ = '\0';
  1088.     *place++ = '\0';
  1089.     *place++ = (char_u) (((unsigned)minval >> 8) & 0377);
  1090.     *place++ = (char_u) (minval & 0377);
  1091.     *place++ = (char_u) (((unsigned)maxval >> 8) & 0377);
  1092.     *place++ = (char_u) (maxval & 0377);
  1093.     regtail(opnd, place);
  1094. }
  1095.  
  1096. /*
  1097.  * regtail - set the next-pointer at the end of a node chain
  1098.  */
  1099.     static void
  1100. regtail(p, val)
  1101.     char_u       *p;
  1102.     char_u       *val;
  1103. {
  1104.     char_u  *scan;
  1105.     char_u  *temp;
  1106.     int        offset;
  1107.  
  1108.     if (p == JUST_CALC_SIZE)
  1109.     return;
  1110.  
  1111.     /* Find last node. */
  1112.     scan = p;
  1113.     for (;;)
  1114.     {
  1115.     temp = regnext(scan);
  1116.     if (temp == NULL)
  1117.         break;
  1118.     scan = temp;
  1119.     }
  1120.  
  1121.     if (OP(scan) == BACK)
  1122.     offset = (int)(scan - val);
  1123.     else
  1124.     offset = (int)(val - scan);
  1125.     *(scan + 1) = (char_u) (((unsigned)offset >> 8) & 0377);
  1126.     *(scan + 2) = (char_u) (offset & 0377);
  1127. }
  1128.  
  1129. /*
  1130.  * regoptail - regtail on operand of first argument; nop if operandless
  1131.  */
  1132.     static void
  1133. regoptail(p, val)
  1134.     char_u       *p;
  1135.     char_u       *val;
  1136. {
  1137.     /* When op is neither BRANCH nor BRACE_COMPLEX0-9, it is "operandless" */
  1138.     if (p == NULL || p == JUST_CALC_SIZE ||
  1139.         (OP(p) != BRANCH &&
  1140.          (OP(p) < BRACE_COMPLEX || OP(p) > BRACE_COMPLEX + 9)))
  1141.     return;
  1142.     regtail(OPERAND(p), val);
  1143. }
  1144.  
  1145. /*
  1146.  * getchr() - get the next character from the pattern. We know about
  1147.  * magic and such, so therefore we need a lexical analyzer.
  1148.  */
  1149.  
  1150. /* static int        curchr; */
  1151. static int    prevchr;
  1152. static int    nextchr;    /* used for ungetchr() */
  1153. /*
  1154.  * Note: prevchr is sometimes -1 when we are not at the start,
  1155.  * eg in /[ ^I]^ the pattern was never found even if it existed, because ^ was
  1156.  * taken to be magic -- webb
  1157.  */
  1158. static int    at_start;    /* True when on the first character */
  1159. static int    prev_at_start;  /* True when on the second character */
  1160.  
  1161.     static void
  1162. initchr(str)
  1163.     char_u *str;
  1164. {
  1165.     regparse = str;
  1166.     curchr = prevchr = nextchr = -1;
  1167.     at_start = TRUE;
  1168.     prev_at_start = FALSE;
  1169. }
  1170.  
  1171.     static int
  1172. peekchr()
  1173. {
  1174.     if (curchr < 0)
  1175.     {
  1176.     switch (curchr = regparse[0])
  1177.     {
  1178.     case '.':
  1179.     /*    case '+':*/
  1180.     /*    case '=':*/
  1181.     case '[':
  1182.     case '~':
  1183.         if (reg_magic)
  1184.         curchr = Magic(curchr);
  1185.         break;
  1186.     case '*':
  1187.         /* * is not magic as the very first character, eg "?*ptr" and when
  1188.          * after '^', eg "/^*ptr" */
  1189.         if (reg_magic && !at_start
  1190.                  && !(prev_at_start && prevchr == Magic('^')))
  1191.         curchr = Magic('*');
  1192.         break;
  1193.     case '^':
  1194.         /* ^ is only magic as the very first character */
  1195.         if (at_start)
  1196.         curchr = Magic('^');
  1197.         break;
  1198.     case '$':
  1199.         /* $ is only magic as the very last char and in front of '\|' */
  1200.         if (regparse[1] == NUL
  1201.                    || (regparse[1] == '\\' && regparse[2] == '|'))
  1202.         curchr = Magic('$');
  1203.         break;
  1204.     case '\\':
  1205.         regparse++;
  1206.         if (regparse[0] == NUL)
  1207.         {
  1208.         curchr = '\\';    /* trailing '\' */
  1209.         --regparse;    /* there is no extra character to skip */
  1210.         }
  1211.         else if (vim_strchr(META, regparse[0]))
  1212.         {
  1213.         /*
  1214.          * META contains everything that may be magic sometimes, except
  1215.          * ^ and $ ("\^" and "\$" are never magic).
  1216.          * We now fetch the next character and toggle its magicness.
  1217.          * Therefore, \ is so meta-magic that it is not in META.
  1218.          */
  1219.         curchr = -1;
  1220.         prev_at_start = at_start;
  1221.         at_start = FALSE;    /* be able to say "/\*ptr" */
  1222.         peekchr();
  1223.         curchr ^= Magic(0);
  1224.         }
  1225.         else if (vim_strchr(REGEXP_ABBR, regparse[0]))
  1226.         {
  1227.         /*
  1228.          * Handle abbreviations, like "\t" for TAB -- webb
  1229.          */
  1230.         curchr = backslash_trans(regparse[0]);
  1231.         }
  1232.         else
  1233.         {
  1234.         /*
  1235.          * Next character can never be (made) magic?
  1236.          * Then backslashing it won't do anything.
  1237.          */
  1238.         curchr = regparse[0];
  1239.         }
  1240.         break;
  1241.     }
  1242.     }
  1243.  
  1244.     return curchr;
  1245. }
  1246.  
  1247.     static void
  1248. skipchr()
  1249. {
  1250.     regparse++;
  1251.     prev_at_start = at_start;
  1252.     at_start = FALSE;
  1253.     prevchr = curchr;
  1254.     curchr = nextchr;        /* use previously unget char, or -1 */
  1255.     nextchr = -1;
  1256. }
  1257.  
  1258.     static int
  1259. getchr()
  1260. {
  1261.     int chr;
  1262.  
  1263.     chr = peekchr();
  1264.     skipchr();
  1265.  
  1266.     return chr;
  1267. }
  1268.  
  1269. /*
  1270.  * put character back. Works only once!
  1271.  */
  1272.     static void
  1273. ungetchr()
  1274. {
  1275.     nextchr = curchr;
  1276.     curchr = prevchr;
  1277.     at_start = prev_at_start;
  1278.     prev_at_start = FALSE;
  1279.     /*
  1280.      * Backup regparse as well; not because we will use what it points at,
  1281.      * but because skipchr() will bump it again.
  1282.      */
  1283.     regparse--;
  1284. }
  1285.  
  1286. /*
  1287.  * read_limits - Read two integers to be taken as a minimum and maximum.
  1288.  * If the first character is '-', then the range is reversed.
  1289.  * Should end with 'end'.  If minval is missing, zero is default, if maxval is
  1290.  * missing, a very big number is the default.
  1291.  */
  1292.     static int
  1293. read_limits(start, end, minval, maxval)
  1294.     int        start;
  1295.     int        end;
  1296.     int        *minval;
  1297.     int        *maxval;
  1298. {
  1299.     int        reverse = FALSE;
  1300.     char_u  *first_char;
  1301.  
  1302.     if (*regparse == '-')
  1303.     {
  1304.     /* Starts with '-', so reverse the range later */
  1305.     regparse++;
  1306.     reverse = TRUE;
  1307.     }
  1308.     first_char = regparse;
  1309.     *minval = getdigits(®parse);
  1310.     if (*regparse == ',')        /* There is a comma */
  1311.     {
  1312.     if (isdigit(*++regparse))
  1313.         *maxval = getdigits(®parse);
  1314.     else
  1315.         *maxval = MAX_LIMIT;
  1316.     }
  1317.     else if (isdigit(*first_char))
  1318.     *maxval = *minval;        /* It was \{n} or \{-n} */
  1319.     else
  1320.     *maxval = MAX_LIMIT;        /* It was \{} or \{-} */
  1321.     if (*regparse == '\\')
  1322.     regparse++;    /* Allow either \{...} or \{...\} */
  1323.     if (       (*regparse != end && *regparse != NUL)
  1324.         || (*maxval == 0 && *minval == 0))
  1325.     {
  1326.     sprintf((char *)IObuff, "Syntax error in \\%c...%c", start, end);
  1327.     emsg(IObuff);
  1328.     rc_did_emsg = TRUE;
  1329.     return FAIL;
  1330.     }
  1331.  
  1332.     /*
  1333.      * Reverse the range if there was a '-', or make sure it is in the right
  1334.      * order otherwise.
  1335.      */
  1336.     if ((!reverse && *minval > *maxval) || (reverse && *minval < *maxval))
  1337.     {
  1338.     int    tmp;
  1339.  
  1340.     tmp = *minval;
  1341.     *minval = *maxval;
  1342.     *maxval = tmp;
  1343.     }
  1344.     skipchr();        /* let's be friends with the lexer again */
  1345.     return OK;
  1346. }
  1347.  
  1348. /*
  1349.  * vim_regexec and friends
  1350.  */
  1351.  
  1352. /*
  1353.  * Global work variables for vim_regexec().
  1354.  */
  1355. static char_u     *reginput;        /* String-input pointer. */
  1356. static char_u     *regbol;        /* Beginning of input, for ^ check. */
  1357. static char_u    **regstartp;        /* Pointer to startp array. */
  1358. static int      need_clear_subexpr;    /* *regstartp end *regendp still need
  1359.                        to be cleared */
  1360.  
  1361. static int    regtry __ARGS((vim_regexp *, char_u *));
  1362. static void    clear_subexpr __ARGS((void));
  1363. static int    regmatch __ARGS((char_u *));
  1364. static int    regrepeat __ARGS((char_u *));
  1365.  
  1366. #ifdef DEBUG
  1367. int        regnarrate = 0;
  1368. #endif
  1369.  
  1370. /*
  1371.  * vim_regexec - match a regexp against a string
  1372.  * Uses current value of reg_ic.
  1373.  * Return non-zero if there is a match.
  1374.  */
  1375.     int
  1376. vim_regexec(prog, string, at_bol)
  1377.     vim_regexp    *prog;
  1378.     char_u    *string;
  1379.     int        at_bol;
  1380. {
  1381.     char_u    *s;
  1382.  
  1383.     /* Be paranoid... */
  1384.     if (prog == NULL || string == NULL)
  1385.     {
  1386.     emsg(e_null);
  1387.     rc_did_emsg = TRUE;
  1388.     return 0;
  1389.     }
  1390.     /* Check validity of program. */
  1391.     if (UCHARAT(prog->program) != MAGIC)
  1392.     {
  1393.     emsg(e_re_corr);
  1394.     rc_did_emsg = TRUE;
  1395.     return 0;
  1396.     }
  1397.     /* If there is a "must appear" string, look for it. */
  1398.     if (prog->regmust != NULL)
  1399.     {
  1400.     s = string;
  1401.     while ((s = cstrchr(s, prog->regmust[0])) != NULL)
  1402.     {
  1403.         if (cstrncmp(s, prog->regmust, prog->regmlen) == 0)
  1404.         break;        /* Found it. */
  1405.         s++;
  1406.     }
  1407.     if (s == NULL)        /* Not present. */
  1408.         return 0;
  1409.     }
  1410.     /* Mark beginning of line for ^ . */
  1411.     if (at_bol)
  1412.     regbol = string;    /* is possible to match bol */
  1413.     else
  1414.     regbol = NULL;        /* we aren't there, so don't match it */
  1415.  
  1416.     /* Simplest case:  anchored match need be tried only once. */
  1417.     if (prog->reganch)
  1418.     {
  1419.     if (prog->regstart != '\0' && prog->regstart != string[0] &&
  1420.         (!reg_ic || TO_LOWER(prog->regstart) != TO_LOWER(string[0])))
  1421.         return 0;
  1422.     return regtry(prog, string);
  1423.     }
  1424.  
  1425.     /* Messy cases:  unanchored match. */
  1426.     s = string;
  1427.     if (prog->regstart != '\0')
  1428.     /* We know what char it must start with. */
  1429.     while ((s = cstrchr(s, prog->regstart)) != NULL)
  1430.     {
  1431.         if (regtry(prog, s))
  1432.         return 1;
  1433.         s++;
  1434.     }
  1435.     else
  1436.     /* We don't -- general case. */
  1437.     do
  1438.     {
  1439.         if (regtry(prog, s))
  1440.         return 1;
  1441.     } while (*s++ != '\0');
  1442.  
  1443.     /* Failure. */
  1444.     return 0;
  1445. }
  1446.  
  1447. /*
  1448.  * regtry - try match at specific point
  1449.  */
  1450.     static int            /* 0 failure, 1 success */
  1451. regtry(prog, string)
  1452.     vim_regexp       *prog;
  1453.     char_u       *string;
  1454. {
  1455.     reginput = string;
  1456.     regstartp = prog->startp;
  1457.     regendp = prog->endp;
  1458.     need_clear_subexpr = TRUE;
  1459.  
  1460.     if (regmatch(prog->program + 1))
  1461.     {
  1462.     clear_subexpr();
  1463.     prog->startp[0] = string;
  1464.     prog->endp[0] = reginput;
  1465.     return 1;
  1466.     }
  1467.     else
  1468.     return 0;
  1469. }
  1470.  
  1471. /*
  1472.  * Clear the subexpressions, if this wasn't done yet.
  1473.  * This construction is used to clear the subexpressions only when they are
  1474.  * used (to increase speed).
  1475.  */
  1476.     static void
  1477. clear_subexpr()
  1478. {
  1479.     if (need_clear_subexpr)
  1480.     {
  1481.     vim_memset(regstartp, 0, sizeof(char_u *) * NSUBEXP);
  1482.     vim_memset(regendp, 0, sizeof(char_u *) * NSUBEXP);
  1483.     need_clear_subexpr = FALSE;
  1484.     }
  1485. }
  1486.  
  1487. /*
  1488.  * regmatch - main matching routine
  1489.  *
  1490.  * Conceptually the strategy is simple: Check to see whether the current
  1491.  * node matches, call self recursively to see whether the rest matches,
  1492.  * and then act accordingly.  In practice we make some effort to avoid
  1493.  * recursion, in particular by going through "ordinary" nodes (that don't
  1494.  * need to know whether the rest of the match failed) by a loop instead of
  1495.  * by recursion.
  1496.  */
  1497.     static int            /* 0 failure, 1 success */
  1498. regmatch(prog)
  1499.     char_u       *prog;
  1500. {
  1501.     char_u        *scan;    /* Current node. */
  1502.     char_u        *next;    /* Next node. */
  1503.     int            minval = -1;
  1504.     int            maxval = -1;
  1505.  
  1506.     scan = prog;
  1507. #ifdef DEBUG
  1508.     if (scan != NULL && regnarrate)
  1509.     {
  1510.     mch_errmsg(regprop(scan));
  1511.     mch_errmsg("(\n");
  1512.     }
  1513. #endif
  1514.     while (scan != NULL)
  1515.     {
  1516. #ifdef DEBUG
  1517.     if (regnarrate)
  1518.     {
  1519.         mch_errmsg(regprop(scan));
  1520.         mch_errmsg("...\n");
  1521.     }
  1522. #endif
  1523.     next = regnext(scan);
  1524.     switch (OP(scan))
  1525.     {
  1526.       case BOL:
  1527.         if (reginput != regbol)
  1528.         return 0;
  1529.         break;
  1530.       case EOL:
  1531.         if (*reginput != '\0')
  1532.         return 0;
  1533.         break;
  1534.       case BOW:    /* \<word; reginput points to w */
  1535.         if (reginput != regbol && vim_iswordc(reginput[-1]))
  1536.         return 0;
  1537.         if (!reginput[0] || !vim_iswordc(reginput[0]))
  1538.         return 0;
  1539.         break;
  1540.       case EOW:    /* word\>; reginput points after d */
  1541.         if (reginput == regbol || !vim_iswordc(reginput[-1]))
  1542.         return 0;
  1543.         if (reginput[0] && vim_iswordc(reginput[0]))
  1544.         return 0;
  1545.         break;
  1546.       case ANY:
  1547.         if (*reginput == '\0')
  1548.         return 0;
  1549.         reginput++;
  1550.         break;
  1551.       case IDENT:
  1552.         if (!vim_isIDc(*reginput))
  1553.         return 0;
  1554.         reginput++;
  1555.         break;
  1556.       case WORD:
  1557.         if (!vim_iswordc(*reginput))
  1558.         return 0;
  1559.         reginput++;
  1560.         break;
  1561.       case FNAME:
  1562.         if (!vim_isfilec(*reginput))
  1563.         return 0;
  1564.         reginput++;
  1565.         break;
  1566.       case PRINT:
  1567.         if (charsize(*reginput) != 1)
  1568.         return 0;
  1569.         reginput++;
  1570.         break;
  1571.       case SIDENT:
  1572.         if (isdigit(*reginput) || !vim_isIDc(*reginput))
  1573.         return 0;
  1574.         reginput++;
  1575.         break;
  1576.       case SWORD:
  1577.         if (isdigit(*reginput) || !vim_iswordc(*reginput))
  1578.         return 0;
  1579.         reginput++;
  1580.         break;
  1581.       case SFNAME:
  1582.         if (isdigit(*reginput) || !vim_isfilec(*reginput))
  1583.         return 0;
  1584.         reginput++;
  1585.         break;
  1586.       case SPRINT:
  1587.         if (isdigit(*reginput) || charsize(*reginput) != 1)
  1588.         return 0;
  1589.         reginput++;
  1590.         break;
  1591.       case WHITE:
  1592.         if (!vim_iswhite(*reginput))
  1593.         return 0;
  1594.         reginput++;
  1595.         break;
  1596.       case NWHITE:
  1597.         if (*reginput == NUL || vim_iswhite(*reginput))
  1598.         return 0;
  1599.         reginput++;
  1600.         break;
  1601.       case EXACTLY:
  1602.         {
  1603.         int        len;
  1604.         char_u        *opnd;
  1605.  
  1606.         opnd = OPERAND(scan);
  1607.         /* Inline the first character, for speed. */
  1608.         if (*opnd != *reginput
  1609.             && (!reg_ic || TO_LOWER(*opnd) != TO_LOWER(*reginput)))
  1610.             return 0;
  1611.         len = STRLEN(opnd);
  1612.         if (len > 1 && cstrncmp(opnd, reginput, len) != 0)
  1613.             return 0;
  1614.         reginput += len;
  1615.         }
  1616.         break;
  1617.       case ANYOF:
  1618.         if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) == NULL)
  1619.         return 0;
  1620.         reginput++;
  1621.         break;
  1622.       case ANYBUT:
  1623.         if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) != NULL)
  1624.         return 0;
  1625.         reginput++;
  1626.         break;
  1627.       case NOTHING:
  1628.         break;
  1629.       case BACK:
  1630.         break;
  1631.       case MOPEN + 1:
  1632.       case MOPEN + 2:
  1633.       case MOPEN + 3:
  1634.       case MOPEN + 4:
  1635.       case MOPEN + 5:
  1636.       case MOPEN + 6:
  1637.       case MOPEN + 7:
  1638.       case MOPEN + 8:
  1639.       case MOPEN + 9:
  1640.         {
  1641.         int        no;
  1642.         char_u        *save;
  1643.  
  1644.         clear_subexpr();
  1645.         no = OP(scan) - MOPEN;
  1646.         save = regstartp[no];
  1647.         regstartp[no] = reginput; /* Tentatively */
  1648. #ifdef DEBUG
  1649.         if (regnarrate)
  1650.             printf("MOPEN  %d pre  @'%s' ('%s' )'%s'\n",
  1651.             no, save,
  1652.             regstartp[no] ? (char *)regstartp[no] : "NULL",
  1653.             regendp[no] ? (char *)regendp[no] : "NULL");
  1654. #endif
  1655.  
  1656.         if (regmatch(next))
  1657.         {
  1658. #ifdef DEBUG
  1659.             if (regnarrate)
  1660.             printf("MOPEN  %d post @'%s' ('%s' )'%s'\n",
  1661.                 no, save,
  1662.                 regstartp[no] ? (char *)regstartp[no] : "NULL",
  1663.                 regendp[no] ? (char *)regendp[no] : "NULL");
  1664. #endif
  1665.             return 1;
  1666.         }
  1667.         regstartp[no] = save;        /* We were wrong... */
  1668.         return 0;
  1669.         }
  1670.         /* break; Not Reached */
  1671.       case MCLOSE + 1:
  1672.       case MCLOSE + 2:
  1673.       case MCLOSE + 3:
  1674.       case MCLOSE + 4:
  1675.       case MCLOSE + 5:
  1676.       case MCLOSE + 6:
  1677.       case MCLOSE + 7:
  1678.       case MCLOSE + 8:
  1679.       case MCLOSE + 9:
  1680.         {
  1681.         int        no;
  1682.         char_u        *save;
  1683.  
  1684.         clear_subexpr();
  1685.         no = OP(scan) - MCLOSE;
  1686.         save = regendp[no];
  1687.         regendp[no] = reginput; /* Tentatively */
  1688. #ifdef DEBUG
  1689.         if (regnarrate)
  1690.             printf("MCLOSE %d pre  @'%s' ('%s' )'%s'\n",
  1691.             no, save,
  1692.             regstartp[no] ? (char *)regstartp[no] : "NULL",
  1693.             regendp[no] ? (char *)regendp[no] : "NULL");
  1694. #endif
  1695.  
  1696.         if (regmatch(next))
  1697.         {
  1698. #ifdef DEBUG
  1699.             if (regnarrate)
  1700.             printf("MCLOSE %d post @'%s' ('%s' )'%s'\n",
  1701.                 no, save,
  1702.                 regstartp[no] ? (char *)regstartp[no] : "NULL",
  1703.                 regendp[no] ? (char *)regendp[no] : "NULL");
  1704. #endif
  1705.             return 1;
  1706.         }
  1707.         regendp[no] = save;    /* We were wrong... */
  1708.         return 0;
  1709.         }
  1710.         /* break; Not Reached */
  1711.       case BACKREF + 1:
  1712.       case BACKREF + 2:
  1713.       case BACKREF + 3:
  1714.       case BACKREF + 4:
  1715.       case BACKREF + 5:
  1716.       case BACKREF + 6:
  1717.       case BACKREF + 7:
  1718.       case BACKREF + 8:
  1719.       case BACKREF + 9:
  1720.         {
  1721.         int    no;
  1722.         int    len;
  1723.  
  1724.         clear_subexpr();
  1725.         no = OP(scan) - BACKREF;
  1726.         if (regendp[no] != NULL)
  1727.         {
  1728.             len = (int)(regendp[no] - regstartp[no]);
  1729.             if (cstrncmp(regstartp[no], reginput, len) != 0)
  1730.             return 0;
  1731.             reginput += len;
  1732.         }
  1733.         else
  1734.         {
  1735.             /*emsg("backref to 0-repeat");*/
  1736.             /*return 0;*/
  1737.         }
  1738.         }
  1739.         break;
  1740.       case BRANCH:
  1741.         {
  1742.         char_u        *save;
  1743.  
  1744.         if (OP(next) != BRANCH) /* No choice. */
  1745.             next = OPERAND(scan);    /* Avoid recursion. */
  1746.         else
  1747.         {
  1748.             do
  1749.             {
  1750.             save = reginput;
  1751.             if (regmatch(OPERAND(scan)))
  1752.                 return 1;
  1753.             reginput = save;
  1754.             scan = regnext(scan);
  1755.             } while (scan != NULL && OP(scan) == BRANCH);
  1756.             return 0;
  1757.             /* NOTREACHED */
  1758.         }
  1759.         }
  1760.         break;
  1761.       case BRACE_LIMITS:
  1762.         {
  1763.         int    no;
  1764.  
  1765.         if (OP(next) == BRACE_SIMPLE)
  1766.         {
  1767.             minval = OPERAND_MIN(scan);
  1768.             maxval = OPERAND_MAX(scan);
  1769.         }
  1770.         else if (OP(next) >= BRACE_COMPLEX &&
  1771.              OP(next) < BRACE_COMPLEX + 10)
  1772.         {
  1773.             no = OP(next) - BRACE_COMPLEX;
  1774.             brace_min[no] = OPERAND_MIN(scan);
  1775.             brace_max[no] = OPERAND_MAX(scan);
  1776.             brace_count[no] = 0;
  1777.         }
  1778.         else
  1779.         {
  1780.             emsg(e_internal);        /* Shouldn't happen */
  1781.             return 0;
  1782.         }
  1783.         }
  1784.         break;
  1785.       case BRACE_COMPLEX + 0:
  1786.       case BRACE_COMPLEX + 1:
  1787.       case BRACE_COMPLEX + 2:
  1788.       case BRACE_COMPLEX + 3:
  1789.       case BRACE_COMPLEX + 4:
  1790.       case BRACE_COMPLEX + 5:
  1791.       case BRACE_COMPLEX + 6:
  1792.       case BRACE_COMPLEX + 7:
  1793.       case BRACE_COMPLEX + 8:
  1794.       case BRACE_COMPLEX + 9:
  1795.         {
  1796.         int        no;
  1797.         char_u        *save;
  1798.  
  1799.         no = OP(scan) - BRACE_COMPLEX;
  1800.         ++brace_count[no];
  1801.  
  1802.         /* If not matched enough times yet, try one more */
  1803.         if (brace_count[no] <= (brace_min[no] <= brace_max[no]
  1804.                     ? brace_min[no] : brace_max[no]))
  1805.         {
  1806.             save = reginput;
  1807.             if (regmatch(OPERAND(scan)))
  1808.             return 1;
  1809.             reginput = save;
  1810.             --brace_count[no];    /* failed, decrement match count */
  1811.             return 0;
  1812.         }
  1813.  
  1814.         /* If matched enough times, may try matching some more */
  1815.         if (brace_min[no] <= brace_max[no])
  1816.         {
  1817.             /* Range is the normal way around, use longest match */
  1818.             if (brace_count[no] <= brace_max[no])
  1819.             {
  1820.             save = reginput;
  1821.             if (regmatch(OPERAND(scan)))
  1822.                 return 1;        /* matched some more times */
  1823.             reginput = save;
  1824.             --brace_count[no];  /* matched just enough times */
  1825.             /* continue with the items after \{} */
  1826.             }
  1827.         }
  1828.         else
  1829.         {
  1830.             /* Range is backwards, use shortest match first */
  1831.             if (brace_count[no] <= brace_min[no])
  1832.             {
  1833.             save = reginput;
  1834.             if (regmatch(next))
  1835.                 return 1;
  1836.             reginput = save;
  1837.             next = OPERAND(scan);
  1838.             /* must try to match one more item */
  1839.             }
  1840.         }
  1841.         }
  1842.         break;
  1843.  
  1844.       case BRACE_SIMPLE:
  1845.       case STAR:
  1846.       case PLUS:
  1847.         {
  1848.         int    nextch;
  1849.         int    nextch_ic;
  1850.         int    no;
  1851.         char_u    *save;
  1852.  
  1853.         /*
  1854.          * Lookahead to avoid useless match attempts when we know
  1855.          * what character comes next.
  1856.          */
  1857.         if (OP(next) == EXACTLY)
  1858.         {
  1859.             nextch = *OPERAND(next);
  1860.             if (reg_ic)
  1861.             {
  1862.             if (isupper(nextch))
  1863.                 nextch_ic = TO_LOWER(nextch);
  1864.             else
  1865.                 nextch_ic = TO_UPPER(nextch);
  1866.             }
  1867.             else
  1868.             nextch_ic = nextch;
  1869.         }
  1870.         else
  1871.         {
  1872.             nextch = '\0';
  1873.             nextch_ic = '\0';
  1874.         }
  1875.         if (OP(scan) != BRACE_SIMPLE)
  1876.         {
  1877.             minval = (OP(scan) == STAR) ? 0 : 1;
  1878.             maxval = MAX_LIMIT;
  1879.         }
  1880.  
  1881.         save = reginput;
  1882.         no = regrepeat(OPERAND(scan));
  1883.         if (minval <= maxval)
  1884.         {
  1885.             /* Range is the normal way around, use longest match */
  1886.             if (no > maxval)
  1887.             {
  1888.             no = maxval;
  1889.             reginput = save + no;
  1890.             }
  1891.             while (no >= minval)
  1892.             {
  1893.             /* If it could work, try it. */
  1894.             if (nextch == '\0' || *reginput == nextch
  1895.                             || *reginput == nextch_ic)
  1896.                 if (regmatch(next))
  1897.                 return 1;
  1898.             /* Couldn't or didn't -- back up. */
  1899.             no--;
  1900.             reginput = save + no;
  1901.             }
  1902.         }
  1903.         else
  1904.         {
  1905.             /* Range is backwards, use shortest match first */
  1906.             if (no < maxval)
  1907.             return 0;
  1908.             if (minval > no)
  1909.             minval = no;    /* Actually maximum value */
  1910.             no = maxval;
  1911.             reginput = save + no;
  1912.             while (no <= minval)
  1913.             {
  1914.             /* If it could work, try it. */
  1915.             if (nextch == '\0' || *reginput == nextch
  1916.                             || *reginput == nextch_ic)
  1917.                 if (regmatch(next))
  1918.                 return 1;
  1919.             /* Couldn't or didn't -- try longer match. */
  1920.             no++;
  1921.             reginput = save + no;
  1922.             }
  1923.         }
  1924.         return 0;
  1925.         }
  1926.         /* break; Not Reached */
  1927.       case END:
  1928.         return 1;        /* Success! */
  1929.         /* break; Not Reached */
  1930.       default:
  1931.         emsg(e_re_corr);
  1932. #ifdef DEBUG
  1933.         printf("Illegal op code %d\n", OP(scan));
  1934. #endif
  1935.         return 0;
  1936.         /* break; Not Reached */
  1937.     }
  1938.  
  1939.     scan = next;
  1940.     }
  1941.  
  1942.     /*
  1943.      * We get here only if there's trouble -- normally "case END" is the
  1944.      * terminating point.
  1945.      */
  1946.     emsg(e_re_corr);
  1947. #ifdef DEBUG
  1948.     printf("Premature EOL\n");
  1949. #endif
  1950.     return 0;
  1951. }
  1952.  
  1953. /*
  1954.  * regrepeat - repeatedly match something simple, report how many
  1955.  */
  1956.     static int
  1957. regrepeat(p)
  1958.     char_u       *p;
  1959. {
  1960.     int        count = 0;
  1961.     char_u  *scan;
  1962.     char_u  *opnd;
  1963.  
  1964.     scan = reginput;
  1965.     opnd = OPERAND(p);
  1966.     switch (OP(p))
  1967.     {
  1968.       case ANY:
  1969.     count = STRLEN(scan);
  1970.     scan += count;
  1971.     break;
  1972.       case IDENT:
  1973.     for (count = 0; vim_isIDc(*scan); ++count)
  1974.         ++scan;
  1975.     break;
  1976.       case WORD:
  1977.     for (count = 0; vim_iswordc(*scan); ++count)
  1978.         ++scan;
  1979.     break;
  1980.       case FNAME:
  1981.     for (count = 0; vim_isfilec(*scan); ++count)
  1982.         ++scan;
  1983.     break;
  1984.       case PRINT:
  1985.     for (count = 0; charsize(*scan) == 1; ++count)
  1986.         ++scan;
  1987.     break;
  1988.       case SIDENT:
  1989.     for (count = 0; !isdigit(*scan) && vim_isIDc(*scan); ++count)
  1990.         ++scan;
  1991.     break;
  1992.       case SWORD:
  1993.     for (count = 0; !isdigit(*scan) && vim_iswordc(*scan); ++count)
  1994.         ++scan;
  1995.     break;
  1996.       case SFNAME:
  1997.     for (count = 0; !isdigit(*scan) && vim_isfilec(*scan); ++count)
  1998.         ++scan;
  1999.     break;
  2000.       case SPRINT:
  2001.     for (count = 0; !isdigit(*scan) && charsize(*scan) == 1; ++count)
  2002.         ++scan;
  2003.     break;
  2004.       case WHITE:
  2005.     for (count = 0; vim_iswhite(*scan); ++count)
  2006.         ++scan;
  2007.     break;
  2008.       case NWHITE:
  2009.     for (count = 0; *scan != NUL && !vim_iswhite(*scan); ++count)
  2010.         ++scan;
  2011.     break;
  2012.       case EXACTLY:
  2013.     {
  2014.         int        cu, cl;
  2015.  
  2016.         if (reg_ic)
  2017.         {
  2018.         cu = TO_UPPER(*opnd);
  2019.         cl = TO_LOWER(*opnd);
  2020.         while (*scan == cu || *scan == cl)
  2021.         {
  2022.             count++;
  2023.             scan++;
  2024.         }
  2025.         }
  2026.         else
  2027.         {
  2028.         cu = *opnd;
  2029.         while (*scan == cu)
  2030.         {
  2031.             count++;
  2032.             scan++;
  2033.         }
  2034.         }
  2035.         break;
  2036.     }
  2037.       case ANYOF:
  2038.     while (*scan != '\0' && cstrchr(opnd, *scan) != NULL)
  2039.     {
  2040.         count++;
  2041.         scan++;
  2042.     }
  2043.     break;
  2044.       case ANYBUT:
  2045.     while (*scan != '\0' && cstrchr(opnd, *scan) == NULL)
  2046.     {
  2047.         count++;
  2048.         scan++;
  2049.     }
  2050.     break;
  2051.       default:            /* Oh dear.  Called inappropriately. */
  2052.     emsg(e_re_corr);
  2053. #ifdef DEBUG
  2054.     printf("Called regrepeat with op code %d\n", OP(p));
  2055. #endif
  2056.     count = 0;        /* Best compromise. */
  2057.     break;
  2058.     }
  2059.     reginput = scan;
  2060.  
  2061.     return count;
  2062. }
  2063.  
  2064. /*
  2065.  * regnext - dig the "next" pointer out of a node
  2066.  */
  2067.     static char_u *
  2068. regnext(p)
  2069.     char_u  *p;
  2070. {
  2071.     int        offset;
  2072.  
  2073.     if (p == JUST_CALC_SIZE)
  2074.     return NULL;
  2075.  
  2076.     offset = NEXT(p);
  2077.     if (offset == 0)
  2078.     return NULL;
  2079.  
  2080.     if (OP(p) == BACK)
  2081.     return p - offset;
  2082.     else
  2083.     return p + offset;
  2084. }
  2085.  
  2086. #ifdef DEBUG
  2087.  
  2088. /*
  2089.  * regdump - dump a regexp onto stdout in vaguely comprehensible form
  2090.  */
  2091.     static void
  2092. regdump(pattern, r)
  2093.     char_u    *pattern;
  2094.     vim_regexp    *r;
  2095. {
  2096.     char_u  *s;
  2097.     int        op = EXACTLY;    /* Arbitrary non-END op. */
  2098.     char_u  *next;
  2099.  
  2100.     printf("\nregcomp(%s):\n", pattern);
  2101.  
  2102.     s = r->program + 1;
  2103.     while (op != END) {        /* While that wasn't END last time... */
  2104.     op = OP(s);
  2105.     printf("%2d%s", (int)(s - r->program), regprop(s)); /* Where, what. */
  2106.     next = regnext(s);
  2107.     if (next == NULL)    /* Next ptr. */
  2108.         printf("(0)");
  2109.     else
  2110.         printf("(%d)", (int)((s - r->program) + (next - s)));
  2111.     if (op == BRACE_LIMITS)
  2112.     {
  2113.         /* Two short ints */
  2114.         printf(" minval %d, maxval %d", OPERAND_MIN(s), OPERAND_MAX(s));
  2115.         s += 4;
  2116.     }
  2117.     s += 3;
  2118.     if (op == ANYOF || op == ANYBUT || op == EXACTLY)
  2119.     {
  2120.         /* Literal string, where present. */
  2121.         while (*s != '\0')
  2122.         {
  2123.         putchar(*s);
  2124.         s++;
  2125.         }
  2126.         s++;
  2127.     }
  2128.     putchar('\n');
  2129.     }
  2130.  
  2131.     /* Header fields of interest. */
  2132.     if (r->regstart != '\0')
  2133.     printf("start `%c' ", r->regstart);
  2134.     if (r->reganch)
  2135.     printf("anchored ");
  2136.     if (r->regmust != NULL)
  2137.     printf("must have \"%s\"", r->regmust);
  2138.     printf("\n");
  2139. }
  2140.  
  2141. /*
  2142.  * regprop - printable representation of opcode
  2143.  */
  2144.     static char_u *
  2145. regprop(op)
  2146.     char_u       *op;
  2147. {
  2148.     char_u        *p;
  2149.     static char_u   buf[50];
  2150.  
  2151.     (void) strcpy(buf, ":");
  2152.  
  2153.     switch (OP(op))
  2154.     {
  2155.       case BOL:
  2156.     p = "BOL";
  2157.     break;
  2158.       case EOL:
  2159.     p = "EOL";
  2160.     break;
  2161.       case BOW:
  2162.     p = "BOW";
  2163.     break;
  2164.       case EOW:
  2165.     p = "EOW";
  2166.     break;
  2167.       case ANY:
  2168.     p = "ANY";
  2169.     break;
  2170.       case IDENT:
  2171.     p = "IDENT";
  2172.     break;
  2173.       case WORD:
  2174.     p = "WORD";
  2175.     break;
  2176.       case FNAME:
  2177.     p = "FNAME";
  2178.     break;
  2179.       case PRINT:
  2180.     p = "PRINT";
  2181.     break;
  2182.       case SIDENT:
  2183.     p = "SIDENT";
  2184.     break;
  2185.       case SWORD:
  2186.     p = "SWORD";
  2187.     break;
  2188.       case SFNAME:
  2189.     p = "SFNAME";
  2190.     break;
  2191.       case SPRINT:
  2192.     p = "SPRINT";
  2193.     break;
  2194.       case WHITE:
  2195.     p = "WHITE";
  2196.     break;
  2197.       case NWHITE:
  2198.     p = "NWHITE";
  2199.     break;
  2200.       case ANYOF:
  2201.     p = "ANYOF";
  2202.     break;
  2203.       case ANYBUT:
  2204.     p = "ANYBUT";
  2205.     break;
  2206.       case BRANCH:
  2207.     p = "BRANCH";
  2208.     break;
  2209.       case EXACTLY:
  2210.     p = "EXACTLY";
  2211.     break;
  2212.       case NOTHING:
  2213.     p = "NOTHING";
  2214.     break;
  2215.       case BACK:
  2216.     p = "BACK";
  2217.     break;
  2218.       case END:
  2219.     p = "END";
  2220.     break;
  2221.       case MOPEN + 1:
  2222.       case MOPEN + 2:
  2223.       case MOPEN + 3:
  2224.       case MOPEN + 4:
  2225.       case MOPEN + 5:
  2226.       case MOPEN + 6:
  2227.       case MOPEN + 7:
  2228.       case MOPEN + 8:
  2229.       case MOPEN + 9:
  2230.     sprintf(buf + STRLEN(buf), "MOPEN%d", OP(op) - MOPEN);
  2231.     p = NULL;
  2232.     break;
  2233.       case MCLOSE + 1:
  2234.       case MCLOSE + 2:
  2235.       case MCLOSE + 3:
  2236.       case MCLOSE + 4:
  2237.       case MCLOSE + 5:
  2238.       case MCLOSE + 6:
  2239.       case MCLOSE + 7:
  2240.       case MCLOSE + 8:
  2241.       case MCLOSE + 9:
  2242.     sprintf(buf + STRLEN(buf), "MCLOSE%d", OP(op) - MCLOSE);
  2243.     p = NULL;
  2244.     break;
  2245.       case BACKREF + 1:
  2246.       case BACKREF + 2:
  2247.       case BACKREF + 3:
  2248.       case BACKREF + 4:
  2249.       case BACKREF + 5:
  2250.       case BACKREF + 6:
  2251.       case BACKREF + 7:
  2252.       case BACKREF + 8:
  2253.       case BACKREF + 9:
  2254.     sprintf(buf + STRLEN(buf), "BACKREF%d", OP(op) - BACKREF);
  2255.     p = NULL;
  2256.     break;
  2257.       case STAR:
  2258.     p = "STAR";
  2259.     break;
  2260.       case PLUS:
  2261.     p = "PLUS";
  2262.     break;
  2263.       case BRACE_LIMITS:
  2264.     p = "BRACE_LIMITS";
  2265.     break;
  2266.       case BRACE_SIMPLE:
  2267.     p = "BRACE_SIMPLE";
  2268.     break;
  2269.       case BRACE_COMPLEX + 0:
  2270.       case BRACE_COMPLEX + 1:
  2271.       case BRACE_COMPLEX + 2:
  2272.       case BRACE_COMPLEX + 3:
  2273.       case BRACE_COMPLEX + 4:
  2274.       case BRACE_COMPLEX + 5:
  2275.       case BRACE_COMPLEX + 6:
  2276.       case BRACE_COMPLEX + 7:
  2277.       case BRACE_COMPLEX + 8:
  2278.       case BRACE_COMPLEX + 9:
  2279.     sprintf(buf + STRLEN(buf), "BRACE_COMPLEX%d", OP(op) - BRACE_COMPLEX);
  2280.     p = NULL;
  2281.     break;
  2282.       default:
  2283.     sprintf(buf + STRLEN(buf), "corrupt %d", OP(op));
  2284.     p = NULL;
  2285.     break;
  2286.     }
  2287.     if (p != NULL)
  2288.     (void) strcat(buf, p);
  2289.     return buf;
  2290. }
  2291. #endif
  2292.  
  2293. /*
  2294.  * Compare two strings, ignore case if reg_ic set.
  2295.  * Return 0 if strings match, non-zero otherwise.
  2296.  */
  2297.     static int
  2298. cstrncmp(s1, s2, n)
  2299.     char_u    *s1, *s2;
  2300.     int        n;
  2301. {
  2302.     if (!reg_ic)
  2303.     return STRNCMP(s1, s2, n);
  2304.     return STRNICMP(s1, s2, n);
  2305. }
  2306.  
  2307. /*
  2308.  * cstrchr: This function is used a lot for simple searches, keep it fast!
  2309.  */
  2310.     static char_u *
  2311. cstrchr(s, c)
  2312.     char_u    *s;
  2313.     int        c;
  2314. {
  2315.     char_u    *p;
  2316.     int        cc;
  2317.  
  2318.     if (!reg_ic)
  2319.     return vim_strchr(s, c);
  2320.  
  2321.     /* tolower() and toupper() can be slow, comparing twice should be a lot
  2322.      * faster (esp. when using MS Visual C++!) */
  2323.     if (isupper(c))
  2324.     cc = TO_LOWER(c);
  2325.     else if (islower(c))
  2326.     cc = TO_UPPER(c);
  2327.     else
  2328.     return vim_strchr(s, c);
  2329.  
  2330.     for (p = s; *p; ++p)
  2331.     if (*p == c || *p == cc)
  2332.         return p;
  2333.     return NULL;
  2334. }
  2335.  
  2336. /***************************************************************
  2337.  *              regsub stuff                   *
  2338.  ***************************************************************/
  2339.  
  2340. /* This stuff below really confuses cc on an SGI -- webb */
  2341. #ifdef __sgi
  2342. # undef __ARGS
  2343. # define __ARGS(x)  ()
  2344. #endif
  2345.  
  2346. /*
  2347.  * We should define ftpr as a pointer to a function returning a pointer to
  2348.  * a function returning a pointer to a function ...
  2349.  * This is impossible, so we declare a pointer to a function returning a
  2350.  * pointer to a function returning void. This should work for all compilers.
  2351.  */
  2352. typedef void (*(*fptr) __ARGS((char_u *, int)))();
  2353.  
  2354. static fptr do_upper __ARGS((char_u *, int));
  2355. static fptr do_Upper __ARGS((char_u *, int));
  2356. static fptr do_lower __ARGS((char_u *, int));
  2357. static fptr do_Lower __ARGS((char_u *, int));
  2358.  
  2359.     static fptr
  2360. do_upper(d, c)
  2361.     char_u *d;
  2362.     int c;
  2363. {
  2364.     *d = TO_UPPER(c);
  2365.  
  2366.     return (fptr)NULL;
  2367. }
  2368.  
  2369.     static fptr
  2370. do_Upper(d, c)
  2371.     char_u *d;
  2372.     int c;
  2373. {
  2374.     *d = TO_UPPER(c);
  2375.  
  2376.     return (fptr)do_Upper;
  2377. }
  2378.  
  2379.     static fptr
  2380. do_lower(d, c)
  2381.     char_u *d;
  2382.     int c;
  2383. {
  2384.     *d = TO_LOWER(c);
  2385.  
  2386.     return (fptr)NULL;
  2387. }
  2388.  
  2389.     static fptr
  2390. do_Lower(d, c)
  2391.     char_u *d;
  2392.     int c;
  2393. {
  2394.     *d = TO_LOWER(c);
  2395.  
  2396.     return (fptr)do_Lower;
  2397. }
  2398.  
  2399. /*
  2400.  * regtilde(): Replace tildes in the pattern by the old pattern.
  2401.  *
  2402.  * Short explanation of the tilde: It stands for the previous replacement
  2403.  * pattern.  If that previous pattern also contains a ~ we should go back a
  2404.  * step further...  But we insert the previous pattern into the current one
  2405.  * and remember that.
  2406.  * This still does not handle the case where "magic" changes. TODO?
  2407.  *
  2408.  * The tildes are parsed once before the first call to vim_regsub().
  2409.  */
  2410.     char_u *
  2411. regtilde(source, magic)
  2412.     char_u  *source;
  2413.     int        magic;
  2414. {
  2415.     char_u  *newsub = source;
  2416.     char_u  *tmpsub;
  2417.     char_u  *p;
  2418.     int        len;
  2419.     int        prevlen;
  2420.  
  2421.     for (p = newsub; *p; ++p)
  2422.     {
  2423.     if ((*p == '~' && magic) || (*p == '\\' && *(p + 1) == '~' && !magic))
  2424.     {
  2425.         if (reg_prev_sub != NULL)
  2426.         {
  2427.         /* length = len(newsub) - 1 + len(prev_sub) + 1 */
  2428.         prevlen = STRLEN(reg_prev_sub);
  2429.         tmpsub = alloc((unsigned)(STRLEN(newsub) + prevlen));
  2430.         if (tmpsub != NULL)
  2431.         {
  2432.             /* copy prefix */
  2433.             len = (int)(p - newsub);    /* not including ~ */
  2434.             vim_memmove(tmpsub, newsub, (size_t)len);
  2435.             /* interpretate tilde */
  2436.             vim_memmove(tmpsub + len, reg_prev_sub, (size_t)prevlen);
  2437.             /* copy postfix */
  2438.             if (!magic)
  2439.             ++p;            /* back off \ */
  2440.             STRCPY(tmpsub + len + prevlen, p + 1);
  2441.  
  2442.             if (newsub != source)    /* already allocated newsub */
  2443.             vim_free(newsub);
  2444.             newsub = tmpsub;
  2445.             p = newsub + len + prevlen;
  2446.         }
  2447.         }
  2448.         else if (magic)
  2449.         STRCPY(p, p + 1);        /* remove '~' */
  2450.         else
  2451.         STRCPY(p, p + 2);        /* remove '\~' */
  2452.         --p;
  2453.     }
  2454.     else if (*p == '\\' && p[1])        /* skip escaped characters */
  2455.         ++p;
  2456.     }
  2457.  
  2458.     vim_free(reg_prev_sub);
  2459.     if (newsub != source)    /* newsub was allocated, just keep it */
  2460.     reg_prev_sub = newsub;
  2461.     else            /* no ~ found, need to save newsub  */
  2462.     reg_prev_sub = vim_strsave(newsub);
  2463.     return newsub;
  2464. }
  2465.  
  2466. /*
  2467.  * vim_regsub() - perform substitutions after a regexp match
  2468.  *
  2469.  * If copy is TRUE really copy into dest.
  2470.  * If copy is FALSE nothing is copied, this is just to find out the length of
  2471.  * the result.
  2472.  *
  2473.  * Returns the size of the replacement, including terminating NUL.
  2474.  */
  2475.     int
  2476. vim_regsub(prog, source, dest, copy, magic)
  2477.     vim_regexp       *prog;
  2478.     char_u       *source;
  2479.     char_u       *dest;
  2480.     int            copy;
  2481.     int            magic;
  2482. {
  2483.     char_u    *src;
  2484.     char_u    *dst;
  2485.     char_u    *s;
  2486.     int        c;
  2487.     int        no;
  2488.     fptr    func = (fptr)NULL;
  2489.  
  2490.     if (prog == NULL || source == NULL || dest == NULL)
  2491.     {
  2492.     emsg(e_null);
  2493.     return 0;
  2494.     }
  2495.     if (UCHARAT(prog->program) != MAGIC)
  2496.     {
  2497.     emsg(e_re_corr);
  2498.     return 0;
  2499.     }
  2500.     src = source;
  2501.     dst = dest;
  2502.  
  2503.     while ((c = *src++) != '\0')
  2504.     {
  2505.     no = -1;
  2506.     if (c == '&' && magic)
  2507.         no = 0;
  2508.     else if (c == '\\' && *src != NUL)
  2509.     {
  2510.         if (*src == '&' && !magic)
  2511.         {
  2512.         ++src;
  2513.         no = 0;
  2514.         }
  2515.         else if ('0' <= *src && *src <= '9')
  2516.         {
  2517.         no = *src++ - '0';
  2518.         }
  2519.         else if (vim_strchr((char_u *)"uUlLeE", *src))
  2520.         {
  2521.         switch (*src++)
  2522.         {
  2523.         case 'u':   func = (fptr)do_upper;
  2524.                 continue;
  2525.         case 'U':   func = (fptr)do_Upper;
  2526.                 continue;
  2527.         case 'l':   func = (fptr)do_lower;
  2528.                 continue;
  2529.         case 'L':   func = (fptr)do_Lower;
  2530.                 continue;
  2531.         case 'e':
  2532.         case 'E':   func = (fptr)NULL;
  2533.                 continue;
  2534.         }
  2535.         }
  2536.     }
  2537.     if (no < 0)          /* Ordinary character. */
  2538.     {
  2539.         if (c == '\\' && *src != NUL)
  2540.         {
  2541.         /* Check for abbreviations -- webb */
  2542.         switch (*src)
  2543.         {
  2544.             case 'r':    c = CR;        break;
  2545.             case 'n':    c = NL;        break;
  2546.             case 't':    c = TAB;    break;
  2547.             /* Oh no!  \e already has meaning in subst pat :-( */
  2548.             /* case 'e':    c = ESC;        break; */
  2549.             case 'b':    c = Ctrl('H');    break;
  2550.             default:
  2551.             /* Normal character, not abbreviation */
  2552.             c = *src;
  2553.             break;
  2554.         }
  2555.         src++;
  2556.         }
  2557.         if (copy)
  2558.         {
  2559.         if (func == (fptr)NULL)        /* just copy */
  2560.             *dst = c;
  2561.         else                /* change case */
  2562.             func = (fptr)(func(dst, c));
  2563.                 /* Turbo C complains without the typecast */
  2564.         }
  2565.         dst++;
  2566.     }
  2567.     else if (prog->startp[no] != NULL && prog->endp[no] != NULL)
  2568.     {
  2569.         for (s = prog->startp[no]; s < prog->endp[no]; ++s)
  2570.         {
  2571.         if (copy && *s == '\0') /* we hit NUL. */
  2572.         {
  2573.             emsg(e_re_damg);
  2574.             goto exit;
  2575.         }
  2576.         /*
  2577.          * Insert a CTRL-V in front of a CR, otherwise
  2578.          * it will be replaced by a line break.
  2579.          */
  2580.         if (*s == CR)
  2581.         {
  2582.             if (copy)
  2583.             {
  2584.             dst[0] = Ctrl('V');
  2585.             dst[1] = CR;
  2586.             }
  2587.             dst += 2;
  2588.         }
  2589.         else
  2590.         {
  2591.             if (copy)
  2592.             {
  2593.             if (func == (fptr)NULL)        /* just copy */
  2594.                 *dst = *s;
  2595.             else                /* change case */
  2596.                 func = (fptr)(func(dst, *s));
  2597.                     /* Turbo C complains without the typecast */
  2598.             }
  2599.             ++dst;
  2600.         }
  2601.         }
  2602.     }
  2603.     }
  2604.     if (copy)
  2605.     *dst = '\0';
  2606.  
  2607. exit:
  2608.     return (int)((dst - dest) + 1);
  2609. }
  2610.  
  2611. /*
  2612.  * Return TRUE if "c" is a wildcard character.  Depends on 'magic'.
  2613.  */
  2614.     int
  2615. vim_iswildc(c)
  2616.     int        c;
  2617. {
  2618.     return vim_strchr((char_u *)(p_magic ? ".*~[^$\\" : "^$\\"), c) != NULL;
  2619. }
  2620.